﻿#include <stdio.h>
#include <malloc.h>
#include "state.h"

//对以*p为根的二叉排序树作右旋处理
void R_Rotate(BSTree &p) 
{
    BSTree lc;             
    lc = p->lchild;         //lc指向的*p左子树根结点
    p->lchild = lc->rchild; //rc的右子树挂接为*p的左子树
    lc->rchild = p; p = lc; //p指向新的结点
}

//对以*p为根的二叉排序树作左旋处理
void L_Rotate(BSTree &p) 
{
    BSTree rc;             
    rc = p->rchild;         //rc指向的*p右子树根结点
    p->rchild = rc->lchild; //rc的左子树挂接为*p的右子树
    rc->lchild = p; p = rc; //p指向新的结点
}

//对以指针Ｔ所指结点为根的二叉树作左平衡旋转处理
void LeftBalance(BSTree &T)
{
    BSTree lc,rd;
    lc = T->lchild;          //lc指向*T的左子树根结点
    switch(lc->bf)           //检查*T的左子树的平衡度，并作相应平衡处理
    {
    case LH:                 //新结点插入在*T的左孩子的左子树上，要作单右旋处理
        T->bf = lc->bf = EH;
        R_Rotate(T);  break;
    case RH:                 //新结点插入在*T的左孩子的右子树上，要作双旋处理
        rd = lc->rchild;     //rd指向*T的左孩子的右子树根
        switch(rd->bf)       //修改*T及其左孩子的平衡因子
        {
        case LH:T->bf = RH; lc->bf = EH; break;
        case EH:T->bf = lc->bf = EH; break;
        case RH:T->bf = EH; lc->bf = LH; break;
        }
        rd->bf = EH;
        L_Rotate(T->lchild); //对*T的左子树作左旋平衡处理
        R_Rotate(T);         //对*T作右旋平衡处理
    }
}

//对以指针Ｔ所指结点为根的二叉树作右平衡旋转处理
void RightBalance(BSTree &T)
{
    BSTree rc,ld;
    rc = T->rchild;         //rc指向*T的左子树根结点
    switch(rc->bf)          //检查*T的右子树的平衡度，并作相应平衡处理
    {
    case RH:                //新结点插入在*T的右孩子的右子树上，要作单左旋处理
        T->bf = rc->bf =EH;
        L_Rotate(T); break;
    case LH:                //新结点插入在*T的右孩子的左子树上，要作双旋处理
        ld = rc->lchild;    //ld指向*T的右孩子的左子树根
        switch(ld->bf)      //修改*T及其右孩子的平衡因子
        {
        case LH: T->bf = EH; rc->bf = RH; break;
        case EH: T->bf = rc->bf =EH; break;
        case RH: T->bf = LH; rc->bf = EH; break;
        }
        ld->bf = EH;
        R_Rotate(T->rchild);//对*T的右子树作左旋平衡处理
        L_Rotate(T);        //对*T作左旋平衡处理
    }
}


//插入结点e,若Ｔ中存在和e相同关键字的结点，则插入一个数据元素为e的新结点，并返回１，否则返回０
bool InsertAVL(BSTree &T,int e,bool &taller)
{
    if(!T)//插入新结点，树“长高”，置taller为true
    {
        T = (BSTree)malloc(sizeof(BSTNode)); 
        T->data = e;
		T->time=0;
        T->lchild = T->rchild =NULL;
        T->bf = EH; taller = true;
    }
    else
    {
        if(EQ(e,T->data))                 //树中已存在和有相同关键字的结点
        { taller = false;printf("已存在相同商品\n"); return 0; }//则不再插入
        if(LT(e,T->data))                 //应继续在*T的左子树中进行搜索
        {
            if(!InsertAVL(T->lchild,e,taller)) return 0;//未插入
            if(taller)                    //已插入到*T的左子树中且左子树“长高”
                switch(T->bf)             //检查*T的平衡度
        	{
                  case LH:                //原本左子树比右子树高，需要作左平衡处理
                      LeftBalance(T); taller = false; break;
                  case EH:                //原本左子树、右子等高，现因左子树增高而使树增高
                      T->bf = LH; taller = true; break;
                  case RH:                //原本右子树比左子树高，现左、右子树等高
                      T->bf = EH; taller = false; break;
            }//switch(T->bf)
        }//if
        else                              //应继续在*T的右子树中进行搜索
        {
            if(!InsertAVL(T->rchild,e,taller)) return 0;//未插入
            if(taller)                    //已插入到*T的右子树中且右子树“长高”
                switch(T->bf)             //检查*T的平衡度
        	{
                   case LH:               //原本左子树比右子树高，现左、右子树等高
                       T->bf = EH; taller = false; break;
                   case EH:               //原本左子树、右子等高，现因右子树增高而使树增高
                       T->bf = RH; taller = true; break;
                   case RH:               //原本右子树比左子树高，需要作右平衡处理
                       RightBalance(T); taller = false; break;
            }//switch(T->bf)
        }//else
    }//else
    return 1;
}//InsertAVL

bool InsertAVL1(BSTree &T,int e,bool &taller)
{
    if(!T)//插入新结点，树“长高”，置taller为true
    {
        T = (BSTree)malloc(sizeof(BSTNode)); 
        T->data = e;
		T->time=1;
        T->lchild = T->rchild =NULL;
        T->bf = EH; taller = true;
    }
    else
    {
        if(EQ(e,T->data))                 //树中已存在和有相同关键字的结点
        { taller = false;printf("已存在相同商品\n"); return 0; }//则不再插入
        if(LT(e,T->data))                 //应继续在*T的左子树中进行搜索
        {
            if(!InsertAVL(T->lchild,e,taller)) return 0;//未插入
            if(taller)                    //已插入到*T的左子树中且左子树“长高”
                switch(T->bf)             //检查*T的平衡度
        	{
                  case LH:                //原本左子树比右子树高，需要作左平衡处理
                      LeftBalance(T); taller = false; break;
                  case EH:                //原本左子树、右子等高，现因左子树增高而使树增高
                      T->bf = LH; taller = true; break;
                  case RH:                //原本右子树比左子树高，现左、右子树等高
                      T->bf = EH; taller = false; break;
            }//switch(T->bf)
        }//if
        else                              //应继续在*T的右子树中进行搜索
        {
            if(!InsertAVL(T->rchild,e,taller)) return 0;//未插入
            if(taller)                    //已插入到*T的右子树中且右子树“长高”
                switch(T->bf)             //检查*T的平衡度
        	{
                   case LH:               //原本左子树比右子树高，现左、右子树等高
                       T->bf = EH; taller = false; break;
                   case EH:               //原本左子树、右子等高，现因右子树增高而使树增高
                       T->bf = RH; taller = true; break;
                   case RH:               //原本右子树比左子树高，需要作右平衡处理
                       RightBalance(T); taller = false; break;
            }//switch(T->bf)
        }//else
    }//else
    return 1;
}//InsertAVL

//查找元素key是否在树Ｔ中
bool SearchBST(BSTree &T,int key)
{
    if(!T) return false;
	else if(EQ(key,T->data))
	{
		T->time++;
		printf("找到商品%d(查找次数为%d)",T->data,T->time);
		return true;
	}
    else if(LT(key,T->data)) return SearchBST(T->lchild,key);
    else return SearchBST(T->rchild,key);
}


//按树状打印输出二叉树的元素,m表示结点所在层次,初次调用时m=0
void PrintBST(BSTree T,int m)
{
    int i;
    if(T->rchild) PrintBST(T->rchild,m+1);
    for(i = 1; i<=m; i++)  
        printf("     ");//打印 i 个空格以表示出层次
    printf("%d(%d)\n",T->data,T->time);//打印 T 元素,换行 
    if(T->lchild) 
        PrintBST(T->lchild,m+1);
}

//创建平衡二叉树，（注意：以输入－１为二叉树建立的结束）
void CreatBST(BSTree &T)
{
    int e,m;
    bool taller=false;
    T = NULL;
    printf("\n请输入商品(以-1结束):");
    scanf("%d",&e);getchar();
    while(e != -1)
    {
        InsertAVL(T,e,taller);
        //printf("\n请输入商品(以-1结束):");
        scanf("%d",&e);getchar();taller=false;
    }
    m=0;
    printf("创建结束.\n");
    if(T)  PrintBST(T,m);
    else  printf("无商品！\n");
}

//删除结点时左平衡旋转处理
void LeftBalance_div(BSTree &p,int &shorter)
{
	BSTree  p1,p2;
	if(p->bf==1) //p结点的左子树高，删除结点后p的bf减1,树变矮
	{ p->bf=0; shorter=1; }
	else if(p->bf==0)//p结点左、右子树等高，删除结点后p的bf减1,树高不变
	{ p->bf=-1; shorter=0; }
	else  //p结点的右子树高
	{
		p1=p->rchild;//p1指向p的右子树
		if(p1->bf==0)//p1结点左、右子树等高,删除结点后p的bf为-2,进行左旋处理，树高不变
		{
			L_Rotate(p);
			p1->bf=1; p->bf=-1; shorter=0;
        }
		else if(p1->bf==-1)//p1的右子树高，左旋处理后，树变矮
        {
			L_Rotate(p);
            p1->bf=p->bf=0; shorter=1;
        }
		else //p1的左子树高,进行双旋处理(先右旋后左旋)，树变矮
        {
			p2=p1->lchild;
			p1->lchild=p2->rchild; p2->rchild=p1; p->rchild=p2->lchild; p2->lchild=p;
			if(p2->bf==0)
			{ p->bf=0; p1->bf=0; }
			else if(p2->bf==-1)
			{ p->bf=1;p1->bf=0; }
			else 
			{ p->bf=0;p1->bf=-1; }
            p2->bf=0; p=p2; shorter=1;
		}
  }

}

//删除结点时右平衡旋转处理
void RightBalance_div(BSTree &p,int &shorter)
{
	BSTree  p1,p2;
	if(p->bf==-1)
	{ p->bf=0; shorter=1; }
    else if(p->bf==0)
	{ p->bf=1; shorter=0; }
    else
    { 
		p1=p->lchild;
        if(p1->bf==0)
        {
			R_Rotate(p);
            p1->bf=-1; p->bf=1; shorter=0;
		}
        else if(p1->bf==1)
        {
			R_Rotate(p);
            p1->bf=p->bf=0; shorter=1;
        }
        else
        {
            p2=p1->rchild;
            p1->rchild=p2->lchild; p2->lchild=p1; p->lchild=p2->rchild; p2->rchild=p;
            if(p2->bf==0)
            { p->bf=0; p1->bf=0; }
            else if(p2->bf==1)
            { p->bf=-1; p1->bf=0; }
            else 
            { p->bf=0; p1->bf=1; }
            p2->bf=0; p=p2; shorter=1;
		}
	}
}
//删除结点
void Delete(BSTree q,BSTree  &r,int &shorter)
{
	if(r->rchild==NULL)
    {
		q->data=r->data; q=r;
        r=r->lchild; free(q);
        shorter=1;
	}
    else 
    { 
		Delete(q,r->rchild,shorter);
        if(shorter==1) 
			RightBalance_div(r,shorter);
	}
}

//平衡二叉树的删除操作
int DeleteAVL(BSTree &p,int x,int &shorter)
{
	int k;
    BSTree q;
    if(p==NULL)  { printf("不存在要删除的关键字!!\n"); return 0;}
    else if(x<p->data)//在p的左子树中进行删除
    { 
		k=DeleteAVL(p->lchild,x,shorter);
        if(shorter==1)
			LeftBalance_div(p,shorter);
		return k;
	}
	else if(x>p->data)//在p的右子树中进行删除
    {
		k=DeleteAVL(p->rchild,x,shorter);
		if(shorter==1)
			RightBalance_div(p,shorter);
		return k;
	}
	else
	{
		q=p;
		if(p->rchild==NULL) //右子树空则只需重接它的左子树
		{ p=p->lchild; free(q); shorter=1; }
        else if(p->lchild==NULL)//左子树空则只需重接它的右子树
		{ p=p->rchild; free(q); shorter=1; }
        else//左右子树均不空
        {
			Delete(q,q->lchild,shorter);
			if(shorter==1)
				LeftBalance_div(p,shorter);
			p=q; 
		}
       return 1;
	}
}
